/*
 *  Copyright 2008-2010 NVIDIA Corporation
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

#pragma once

#include <thrust/iterator/iterator_traits.h>
#include <thrust/iterator/iterator_facade.h>
#include <thrust/iterator/iterator_categories.h>
#include <thrust/iterator/detail/minimum_category.h>
#include <thrust/iterator/detail/minimum_space.h>
#include <thrust/tuple.h>
#include <thrust/detail/tuple_meta_transform.h>
#include <thrust/detail/tuple_transform.h>
#include <thrust/detail/type_traits.h>
#include <thrust/detail/device/dereference.h>

namespace thrust {

// forward declare zip_iterator for zip_iterator_base
template<typename IteratorTuple> class zip_iterator;

namespace detail {


// forward declaration of the lambda placeholders
struct _1;
struct _2;


namespace device {


// specialize dereference_result on the lambda placeholder
template<>
struct dereference_result<_1> {
    template <class T>
    struct apply : thrust::detail::device::dereference_result<T> {};
}; // end dereference_result

} // end device


// Functors to be used with tuple algorithms
//
template<typename DiffType>
class advance_iterator {
public:
    __host__ __device__
    advance_iterator(DiffType step) : m_step(step) {}

    template<typename Iterator>
    __host__ __device__
    void operator()(Iterator& it) const
    { it += m_step; }

private:
    DiffType m_step;
}; // end advance_iterator


struct increment_iterator {
    template<typename Iterator>
    __host__ __device__
    void operator()(Iterator& it)
    { ++it; }
}; // end increment_iterator


struct decrement_iterator {
    template<typename Iterator>
    __host__ __device__
    void operator()(Iterator& it)
    { --it; }
}; // end decrement_iterator


struct dereference_iterator {
    template<typename Iterator>
    struct apply {
        typedef typename
        iterator_traits<Iterator>::reference
        type;
    }; // end apply

    template<typename Iterator>
    __host__ __device__
    typename apply<Iterator>::type operator()(Iterator const& it)
    { return *it; }
}; // end dereference_iterator


struct device_dereference_iterator {
    template<typename Iterator>
    struct apply {
        typedef typename
        thrust::detail::device::dereference_result<Iterator>::type
        type;
    }; // end apply

    template<typename Iterator>
    __host__ __device__
    typename apply<Iterator>::type operator()(Iterator const& it)
    { return ::thrust::detail::device::dereference(it); }
}; // end device_dereference_iterator


template<typename IndexType>
struct device_dereference_iterator_with_index {
    template<typename Iterator>
    struct apply {
        typedef typename
        thrust::detail::device::dereference_result<Iterator>::type
        type;
    }; // end apply

    template<typename Iterator>
    __host__ __device__
    typename apply<Iterator>::type operator()(Iterator const& it)
    { return ::thrust::detail::device::dereference(it, n); }

    IndexType n;
}; // end device_dereference_iterator


// The namespace tuple_impl_specific provides two meta-
// algorithms and two algorithms for tuples.
namespace tuple_impl_specific {

// define apply1 for tuple_meta_transform_impl
template<typename UnaryMetaFunctionClass, class Arg>
struct apply1
        : UnaryMetaFunctionClass::template apply<Arg> {
}; // end apply1


// implement support for extremely simple lambda expressions

// if X is not a placeholder expression, lambda returns X unchanged as type
template<typename X>
struct lambda {
    typedef X type;
}; // end lambda

// if X is a placeholder expression, lambda returns a type which can evaluate X as type
template< template <typename> class X >
struct lambda< X<_1> > {
    // type has a member, apply, which applies X to an argument
    struct type {
        template <typename Arg>
        struct apply {
            typedef typename X<Arg>::type type;
        }; // end apply
    }; // end type
}; // end lambda



// define apply2 for tuple_meta_accumulate_impl
template<typename UnaryMetaFunctionClass, class Arg1, class Arg2>
struct apply2
        : UnaryMetaFunctionClass::template apply<Arg1, Arg2> {
}; // end apply2


// Meta-accumulate algorithm for tuples. Note: The template
// parameter StartType corresponds to the initial value in
// ordinary accumulation.
//
template<class Tuple, class BinaryMetaFun, class StartType>
struct tuple_meta_accumulate;

template <
typename Tuple
, class BinaryMetaFun
, typename StartType
>
struct tuple_meta_accumulate_impl {
    typedef typename apply2 <
    // XXX do we need to implement mpl::lambda or not?
    //typename mpl::lambda<BinaryMetaFun>::type
    BinaryMetaFun
    , typename Tuple::head_type
    , typename tuple_meta_accumulate <
    typename Tuple::tail_type
    , BinaryMetaFun
    , StartType
    >::type
    >::type type;
};


template <
typename Tuple
, class BinaryMetaFun
, typename StartType
>
struct tuple_meta_accumulate
        : thrust::detail::eval_if <
        thrust::detail::is_same<Tuple, thrust::null_type>::value
        , thrust::detail::identity_<StartType>
        , tuple_meta_accumulate_impl <
        Tuple
        , BinaryMetaFun
        , StartType
        >
        > { // end eval_if
}; // end tuple_meta_accumulate


// transform algorithm for tuples. The template parameter Fun
// must be a unary functor which is also a unary metafunction
// class that computes its return type based on its argument
// type. For example:
//
// struct to_ptr
// {
//     template <class Arg>
//     struct apply
//     {
//          typedef Arg* type;
//     }
//
//     template <class Arg>
//     Arg* operator()(Arg x);
// };



// for_each algorithm for tuples.
//
template<typename Fun>
__host__ __device__
Fun tuple_for_each(thrust::null_type, Fun f) {
    return f;
} // end tuple_for_each()


template<typename Tuple, typename Fun>
__host__ __device__
Fun tuple_for_each(Tuple& t, Fun f) {
    f(t.get_head());
    return tuple_for_each(t.get_tail(), f);
} // end tuple_for_each()



// Equality of tuples. NOTE: "==" for tuples currently (7/2003)
// has problems under some compilers, so I just do my own.
// No point in bringing in a bunch of #ifdefs here. This is
// going to go away with the next tuple implementation anyway.
//
__host__ __device__
inline bool tuple_equal(thrust::null_type, thrust::null_type)
{ return true; }


template<typename Tuple1, typename Tuple2>
__host__ __device__
bool tuple_equal(Tuple1 const& t1, Tuple2 const& t2) {
    return t1.get_head() == t2.get_head() &&
           tuple_equal(t1.get_tail(), t2.get_tail());
} // end tuple_equal()

} // end end tuple_impl_specific


// define the lambda placeholders for the metafunctions below
struct _1 {};
struct _2 {};


// specialize iterator_reference on the lambda placeholder
template<typename T> struct
        iterator_reference
        : thrust::iterator_reference<T> {
}; // end iterator_reference

template<>
struct iterator_reference<_1> {
    template <class T>
    struct apply : thrust::iterator_reference<T> {};
}; // end iterator_reference

namespace zip_iterator_base_ns {

// specialize iterator_value on the lambda placeholder
template<typename T>
struct iterator_value
        : thrust::iterator_value<T> {
}; // end iterator_value

template<>
struct iterator_value<_1> {
    template <class T>
    struct apply : thrust::iterator_value<T> {};
}; // end iterator_value

} // end zip_iterator_base_ns


// Metafunction to obtain the type of the tuple whose element types
// are the reference types of an iterator tuple.
//
template<typename IteratorTuple>
struct tuple_of_references
        : tuple_meta_transform <
        IteratorTuple,
        iterator_reference
        > {
}; // end tuple_of_references


// Metafunction to obtain the type of the tuple whose element types
// are the device reference types of an iterator tuple.
template<typename IteratorTuple>
struct tuple_of_dereference_result
        : tuple_meta_transform <
        IteratorTuple,
        thrust::detail::device::dereference_result
        > {
}; // end tuple_of_dereference_result


// Metafunction to obtain the type of the tuple whose element types
// are the value_types of an iterator tupel.
//
template<typename IteratorTuple>
struct tuple_of_value_types
        : tuple_meta_transform <
        IteratorTuple,
        iterator_value
        > {
}; // end tuple_of_value_types



// Metafunction to obtain the minimal traversal tag in a tuple
// of iterators.
//
template<typename IteratorTuple>
struct minimum_traversal_category_in_iterator_tuple {
    typedef typename tuple_meta_transform <
    IteratorTuple
    , thrust::iterator_traversal
    >::type tuple_of_traversal_tags;

    typedef typename tuple_impl_specific::tuple_meta_accumulate <
    tuple_of_traversal_tags
    , minimum_category<>
    , thrust::random_access_traversal_tag
    >::type type;
};



// Metafunction to obtain the minimal space tag in a tuple
// of iterators.
template<typename IteratorTuple>
struct minimum_space_in_iterator_tuple {
    typedef typename thrust::detail::tuple_meta_transform <
    IteratorTuple,
    thrust::iterator_space
    >::type tuple_of_space_tags;

    typedef typename tuple_impl_specific::tuple_meta_accumulate <
    tuple_of_space_tags,
    minimum_space<>,
    thrust::any_space_tag
    >::type type;
};


//// We need to call tuple_meta_accumulate with mpl::and_ as the
//// accumulating functor. To this end, we need to wrap it into
//// a struct that has exactly two arguments (that is, template
//// parameters) and not five, like mpl::and_ does.
////
//template<typename Arg1, typename Arg2>
//struct and_with_two_args
//  : mpl::and_<Arg1, Arg2>
//{
//};



///////////////////////////////////////////////////////////////////
//
// Class zip_iterator_base
//
// Builds and exposes the iterator facade type from which the zip
// iterator will be derived.
//
template<typename IteratorTuple>
struct zip_iterator_base {
//private:
    // reference type is the type of the tuple obtained from the
    // iterators' reference types.
    typedef typename tuple_of_references<IteratorTuple>::type reference;

    // Boost's Value type is the same as reference type.
    //typedef reference value_type;
    typedef typename tuple_of_value_types<IteratorTuple>::type value_type;

    // Boost's Pointer type is just value_type *
    //typedef value_type * pointer;
    typedef reference* pointer;

    // Difference type is the first iterator's difference type
    typedef typename thrust::iterator_traits <
    typename thrust::tuple_element<0, IteratorTuple>::type
    >::difference_type difference_type;

    // Iterator space is the minimum space tag in the
    // iterator tuple
    typedef typename
    minimum_space_in_iterator_tuple<IteratorTuple>::type space;

    // Traversal category is the minimum traversal category in the
    // iterator tuple
    typedef typename
    minimum_traversal_category_in_iterator_tuple<IteratorTuple>::type traversal_category;

public:

    // The iterator facade type from which the zip iterator will
    // be derived.
    typedef experimental::iterator_facade <
    zip_iterator<IteratorTuple>,
                 pointer,
                 value_type,
                 space,
                 traversal_category,
                 reference,
                 difference_type
                 > type;
}; // end zip_iterator_base

} // end detail

} // end thrust


